/**
 * @file 45.JumpGameII.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-28
 * 
 * @copyright Copyright (c) 2021
 * 
 * 55.跳跃游戏
 * 45.跳跃游戏II
 * 1005.K 次取反后最大化的数组和
 * 134.加油站
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    cout << '[';
    while (it != Containers.end()) {
        cout << *it << ", ";
        ++it;
    }
    cout << ']';
    cout << endl;
}

class Solution
{
public:
    // 55.
    bool canJump(vector<int> &nums)
    {
        // 贪心策略：维护能跳到最远处index
        int n = nums.size();
        if (n == 1) {
            return true;
        }
        int maxJump = 0; // 最大可达
        for (int i = 0; i < n - 1; ++i) {
            if (maxJump < i) {
                return false;
            }
            maxJump = max(maxJump, i + nums[i]);
            if (maxJump >= n - 1) {
                return true;
            }
        }
        return false;
    }
    // 45.保证一定能跳到尾部，求最小跳跃次数
    int jump(vector<int> &nums)
    {
        // 贪心策略：尽可能跳大一点，局部最优
        // 当i==boundary时更新boundary
        int n = nums.size();
        int boundary = 0, maxJump = 0;
        int step = 0;
        for (int i = 0; i < n - 1; ++i) {
            maxJump = max(maxJump, i + nums[i]);
            if (i == boundary) {
                boundary = maxJump;
                ++step;
            }
        }
        return step;
    }
    // 1005.
    static bool compare(int a, int b)
    {
        return abs(a) < abs(b);
    }
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        // 贪心策略：尽可能把大负数翻正
        // k还有次数就把最小的正数来回折腾
        int n = nums.size();
        std::sort(nums.begin(), nums.end(), compare); // 绝对值排序
        print(nums);
        int i = n - 1;
        while (i >= 0 && k > 0) {
            if (nums[i] == 0) {
                k = 0;
            } else if (nums[i] < 0) {
                nums[i] = -nums[i];
                --k;
            }
            --i;
        }
        if (k > 0 && k % 2 != 0) { // k为正奇数
            nums[0] = -nums[0];
        }
        int sum = 0;
        for (int j = 0; j < n; ++j) {
            sum += nums[j];
        }
        return sum;
    }
    // 134. 返回能环绕一周的出发站，只有一组解
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        // 贪心策略：局部：当前gas[i]-cost[i]要大于零
        int n = gas.size();
        int curSum = 0, totalSum = 0;
        int start = 0;
        for (int i = 0; i < n; ++i) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i]; // 判断能否跑完一圈
            if (curSum < 0) {
                start = i + 1; // curSum小于零，start至少i+1起步
                curSum = 0;
            }
        }
        return totalSum < 0 ? -1 : start;
    }
};

void test55()
{
    vector<int> nums1 = {2, 3, 1, 1, 4};
    vector<int> nums2 = {3, 2, 1, 0, 4};
    cout << Solution().canJump(nums1) << endl;
    cout << Solution().canJump(nums2) << endl;
}

void test45()
{
    vector<int> nums1 = {2, 3, 1, 1, 4};
    vector<int> nums2 = {3, 2, 0, 1, 4};
    cout << Solution().jump(nums1) << endl;
    cout << Solution().jump(nums2) << endl;
}

void test1005()
{
    vector<int> nums1 = {4, 2, 3};
    vector<int> nums2 = {3, -1, 0, 2};
    vector<int> nums3 = {2, -3, -5, 5, -4};
    vector<int> nums4 = {-8, 3, -5, -3, -5, -2};
    // cout << Solution().largestSumAfterKNegations(nums1, 1) << endl;
    // cout << Solution().largestSumAfterKNegations(nums2, 3) << endl;
    // cout << Solution().largestSumAfterKNegations(nums3, 2) << endl;
    cout << Solution().largestSumAfterKNegations(nums4, 6) << endl;
}

int main()
{
    // test55();
    // test45();
    test1005();
    return 0;
}